package com.mc.dp;

/**
 * 
 * @author MC
 *
 */
public class StringDP {
	
	public static void main(String[] args){
		String s1 = "haelllobc";
		String s2 = "haellol";
//		int res = LCString(s1.toCharArray(),s2.toCharArray());
		int res = LUS(s1.toCharArray());
		System.out.println(res);
		
	}
	/*
	 * 最长公共子序列
	 */
	public static int LCS(char[] cha1,char[] cha2){
		
		int[][] mat = new int[cha1.length+1][cha2.length+1];

		for(int i=1;i<mat.length;i++)
			for(int j=1;j<mat[0].length;j++){
				if(cha1[i-1]==cha2[j-1])
					mat[i][j]=mat[i-1][j-1]+1;
				else
					mat[i][j]=Math.max(mat[i][j-1], mat[i-1][j]);
			}
		return mat[cha1.length][cha2.length];
	}
	
	/*
	 * 最长公共子串
	 */
	public static int LCString(char[] cha1,char[] cha2){
		
		int[][] mat = new int[cha1.length+1][cha2.length+1];
		int max = Integer.MIN_VALUE;
		for(int i=1;i<mat.length;i++)
			for(int j=1;j<mat[0].length;j++){
				if(cha1[i-1]==cha2[j-1])
					mat[i][j]=mat[i-1][j-1]+1;
				else{
					mat[i][j]=0;
				}
				if(mat[i][j]>max)
					max = mat[i][j];
			}
		
		return max;
	}
	
	/*
	 * 最长上升子序列
	 */
	public static int LUS(char[] cha1){
		
		int[] len = new int[cha1.length];
		len[0]=1;
		int longest=0;
		for(int i=1;i<cha1.length;i++){
			int max=0;
			for(int j=0;j<i;j++){
				if(cha1[j]<cha1[i]&&len[j]>max){
					max=len[j];
				}
			}
			len[i]=max+1;
			if(len[i]>longest)
				longest = len[i];
		}
		return longest;
	}
	
	/*
	 * 01背包
	 */
    public static int knapsack(int val[], int wt[], int W) {
        //Get the total number of items. 
        //Could be wt.length or val.length. Doesn't matter
        int N = wt.length; 
 
        //Create a matrix. 
        //Items are in rows and weight at in columns +1 on each side
        int[][] V = new int[N + 1][W + 1]; 
 
        //What if the knapsack's capacity is 0 - Set
        //all columns at row 0 to be 0
        for (int col = 0; col <= W; col++) {
            V[0][col] = 0;
        }
 
        //What if there are no items at home.  
        //Fill the first row with 0
        for (int row = 0; row <= N; row++) {
            V[row][0] = 0;
        }
 
        for (int item=1;item<=N;item++){
            //Let's fill the values row by row
            for (int weight=1;weight<=W;weight++){
                //Is the current items weight less
                //than or equal to running weight
                if (wt[item-1]<=weight){
                    //Given a weight, check if the value of the current 
                    //item + value of the item that we could afford 
                    //with the remaining weight is greater than the value
                    //without the current item itself
                    V[item][weight]=Math.max (val[item-1]+V[item-1][weight-wt[item-1]], V[item-1][weight]);
                }
                else {
                    //If the current item's weight is more than the
                    //running weight, just carry forward the value
                    //without the current item
                    V[item][weight]=V[item-1][weight];
                }
            }
 
        }
 
        //Printing the matrix
        for (int[] rows : V) {
            for (int col : rows) {
                System.out.format("%5d", col);
            }
            System.out.println();
        }
 
        return V[N][W];
    }
	
    public static int ZeroOne(int val[],int obj[],int v){
    	int[][] mat = new int[obj.length+1][v+1];
    	
    	
    	for(int item=1;item<mat.length;item++)
    		for(int weight=1;weight<mat[0].length;weight++){
    			if(obj[item-1]<=weight){
    				mat[item][weight]=Math.max(mat[item-1][weight], mat[item-1][weight-obj[item-1]]+val[item-1]);
    			}
    			else{
    				mat[item][weight] = mat[item-1][weight];
    			}
    		}
    	return mat[obj.length][v];
    	
    }
}
